1. Field of the Invention
The present invention relates to the field computation of statistics for populations and more specifically to computation of percentiles of samples of a given population which is changing over time.
2. Description of the Related Art
It is often interesting to be able to express, for a given sample of a population, its position in the population relative to other samples. Often this is expressed as a percentile. For example, if height measurements were taken of all the children in a particular grade school, the student who had as many children taller than him as shorter than him could be said to be in the 50th percentile of the overall population. The population of students in a grade school is a relatively trivial example at least because the population is relatively static over time. If the population was rapidly changing (and, thus, the percentile ranking for each student changing), calculating the percentile for any particular sample becomes non-trivial especially as the rate of change approaches the time it takes to compute the percentile. Typically, computing the percentile of a sample requires obtaining a list of all samples and then sorting the list. This process, especially the sorting of large sets of samples, is compute intensive.
Thus, what is needed is an efficient method and apparatus for computing percentiles of samples of populations which change over time.
A method and apparatus for computing the value at a given percentile and the percentile of a given value is described. In the described system, computing efficiencies are achieved by storing received values in xe2x80x9cbucketsxe2x80x9d and performing percentile calculations based on values in the buckets.